//class Solution {
//public:
//    int minPathSum(vector<vector<int>>& grid) {
//        int n = grid.size();
//        int m = grid[0].size();
//        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
//        dp[0][1] = dp[0][0] = dp[1][0] = 0;
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 1; j <= m; j++)
//            {
//                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
//            }
//        }
//        return dp[n][m];
//    }
//};

//class Solution {
//public:
//    int calculateMinimumHP(vector<vector<int>>& dungeon) {
//        int n = dungeon.size();
//        int m = dungeon[0].size();
//        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
//        dp[n][m - 1] = dp[n - 1][m] = 1;
//        for (int i = n - 1; i >= 0; i--)
//        {
//            for (int j = m - 1; j >= 0; j--)
//            {
//                dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];
//                dp[i][j] = max(1, dp[i][j]);
//            }
//        }
//        return dp[0][0];
//    }
//};

//class Solution {
//public:
//    int massage(vector<int>& nums) {
//        int n = nums.size();
//        if (n == 0) return 0;
//        vector<int> f(n);
//        vector<int> g(n);
//        f[0] = nums[0];
//        for (int i = 1; i < n; i++)
//        {
//            f[i] = g[i - 1] + nums[i];
//            g[i] = max(g[i - 1], f[i - 1]);
//        }
//        return max(f[n - 1], g[n - 1]);
//    }
//};

//class Solution {
//public:
//    int rob(vector<int>& nums) {
//        int n = nums.size();
//        if (n == 1) return nums[0];
//        if (n == 2) return nums[0] > nums[1] ? nums[0] : nums[1];
//        vector<int> f1(n);
//        vector<int> g1(n);
//        f1[2] = nums[2];
//        for (int i = 3; i < n - 1; i++)
//        {
//            f1[i] = g1[i - 1] + nums[i];
//            g1[i] = max(f1[i - 1], g1[i - 1]);
//        }
//        int ret1 = max(f1[n - 2], g1[n - 2]);
//        ret1 += nums[0];
//        //
//        vector<int> f2(n);
//        vector<int> g2(n);
//        f2[1] = nums[1];
//        for (int i = 2; i < n; i++)
//        {
//            f2[i] = g2[i - 1] + nums[i];
//            g2[i] = max(f2[i - 1], g2[i - 1]);
//        }
//        int ret2 = max(f2[n - 1], g2[n - 1]);
//        //
//        return max(ret1, ret2);
//    }
//};

